|
A proper complexity function is a function ''f'' mapping a natural number to a natural number such that: * ''f'' is nondecreasing; * there exists a ''k''-string Turing machine ''M'' such that on any input of length ''n'', ''M'' halts after O(''n'' + ''f''(''n'')) steps, uses O(''f''(''n'')) space, and outputs ''f''(''n'') consecutive blanks. If ''f'' and ''g'' are two proper complexity functions, then ''f'' + ''g'', ''fg'', and 2''f'', are also proper complexity functions. Similar notions include honest function, space-constructible function, and time-constructible function. 〔Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28〕 ==References== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Proper complexity function」の詳細全文を読む スポンサード リンク
|